class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        i = min(a,b) -1

        while n>0:
            i += 1
            if i % a ==0 or i%b ==0:
                n-=1

        return i
## 超时了，解决
## 我的一个改进思路

class Solution1:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        # 先考虑边界

        max_val = max(a, b)
        min_val = min(a, b)
        if max_val % min_val == 0:
            res = n * min_val

        else:
            zb = 0
            za = 0
            while n > 0:
                zb += min_val
                n -= 1
                if n == 0:
                    return zb
                elif zb + min_val > za + max_val:
                    za += max_val
                    n -= 1
                    if n == 0:
                        return za
                    elif za % min_val == 0:
                        n += 1

            res = max(za,zb)
        return res % (10**9 +7)


# 这题真他妈的难啊，二分法，
## 有续 二分
# 上届 min(a,b) * n


if __name__ == '__main__':
    n=3
    a = 8
    b = 9
    solution = Solution()
    val = solution.nthMagicalNumber(n,a,b)
    print(val)

    sulution1 = Solution1()
    val1 = sulution1.nthMagicalNumber(n,a,b)
    print(val1)


    print(10//3)